1. Field of the Invention
The present invention relates to the design of computer systems. More specifically, the present invention relates to a technique that facilitates efficient transactional memory and atomic operations through cache line marking.
2. Related Art
Modern computer systems typically allow several threads to access shared memory simultaneously. Because these threads can potentially perform interfering memory accesses, processor designers have devised mechanisms to ensure that different threads do not interfere with each other while accessing shared memory. For example, atomic operations and transactional execution mechanisms have been developed to ensure that memory locations which are accessed by one thread are protected from accesses by other threads (or in the case of transactional memory, if such interfering accesses occur, an associated transaction fails).
A typical atomic operation is a “read-modify-write” operation which reads a value from a memory location, modifies the value that was read, and writes the modified value back to the memory location. During a read-modify-write operation, a memory location is both read from and written to, and both the read and write must occur without another thread storing to the memory location. To ensure this lack of interference, processors typically first flush pending stores from the processor's store queue and then perform the read-modify-write operation on a cache line containing the memory location. Hence, during the read-modify-write operation, other threads are prevented from gaining access to the cache line.
During transactional execution, a thread executes a special section of code which is designated as “transactional” under the condition that the memory locations accessed by the special section of code must not be interfered with by other threads while the transaction is executing. If such a memory location is interfered with by another thread, the transaction aborts and the transaction is re-executed. For a more detailed explanation of transactional execution, see “Transactional Memory: Architectural Support for Lock-Free Data Structures”, M. Herlihy and E. Moss, in Proc. 20th Intl. Symp. on Computer Architecture, May 1993, and see “LogTM: Log-Based Transactional Memory”, K. Moore, J. Bobba, M. Moravan, M. Hill and D. Wood, in Proc. 12th Symp. on High-Performance Computer Architecture, February 2006. In addition, see U.S. Pat. No. 6,862,664, entitled “Method and Apparatus for Avoiding Locks by Speculatively Executing Critical Sections” by inventors Shailender Chaudhry, Marc Tremblay and Quinn A. Jacobson.
Unfortunately, both transactional execution and atomic operations can be costly to implement. Transactional execution requires dedicated hardware structures to detect and handle interfering data accesses, while atomic instructions require a thread's store queue to be drained every time an atomic instruction is encountered.
Hence, what is needed is a method for facilitating transactional memory and atomic operations without the above-described problems.